package com.ztr.leetcode.day03;

public class MaxArrayValue {
    /**
     * 输入：nums = [2,3,7,9,3]
     * 输出：21
     * 解释：我们可以在数组上执行下述操作：
     * - 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
     * - 选中 i = 1 ，得到数组 nums = [5,16,3] 。
     * - 选中 i = 0 ，得到数组 nums = [21,3] 。
     * 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
     *
     * 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。
     * 将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
     *
     * 1 <= nums.length <= 105
     * 1 <= nums[i] <= 106
     * @param nums
     * @return
     */
    public static long maxArrayValue(int[] nums) {
        int n = nums.length;
        long sum = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sum = nums[i] <= sum ? sum + nums[i] : nums[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        // nums = [2,3,7,9,3]
        int[] nums = {2,3,7,9,3};
        long result  = maxArrayValue(nums);
        System.out.println(result);
    }
}
